#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX=1000;
int up=0;
const int N=5;
const int matrix[N][N]=
{
	{MAX,3,1,5,8},
	{3,MAX,6,7,9},
	{1,6,MAX,4,2},
	{5,7,4,MAX,3},
	{8,9,2,3,MAX}
};
class Node
{
public:
	
	Node()
	{
		x.push_back(1);
		cc=0;
		lcost=0;
	}
	
	Node(const Node &n)
	{
		x=n.x;
		cc=n.cc;
		lcost=n.lcost;
	}
	int getmatrix()
	{
		return matrix[*(x.end()-1)-1][*(x.end()-2)-1];
	}
	bool add(int i)
	{
		x.push_back(i);
		cc+=getmatrix();
		//calcLeast();
		return true;
	}
	bool feasible()
	{
		vector<int>::iterator i;
		
		int temp=*(x.end()-1);
		for (i=x.begin();i!=x.end()-1;i++)
		{
			if (temp==*i)
				return false;
		}
		if(cc>MAX)
			return false;
		if(lcost>up)
			return false;
		calcLeast();
		if (lcost>up)
		{
			return false;
		}
		return true;
		
	}

	int findmin(int a, int b)
	{
		int min;
		int minbut;
		int i;
		if(b==-1)
		{
			min=matrix[a][0]<matrix[a][1]?matrix[a][0]:matrix[a][1];
			minbut=matrix[a][0]+matrix[a][1]-min;
			for(i=2;i<N;i++)
			{
				if(matrix[a][i]<min)
				{
					minbut=min;
					min=matrix[a][i];
					
				}
				else
					if(matrix[a][i]<minbut)
						minbut=matrix[a][i];
			}
			return min+minbut;
		}
		else
		{
			min=MAX;
			for(i=0;i<N;i++)
			{
				if(i==b)
					continue;
				if(matrix[a][i]<min)
					min=matrix[a][i];
			}
			return min;
		}
		
	}

	void calcLeast()
	{
		lcost=cc;
		int i;
		int temp=0;
		int a[N]={0};
		for(vector<int>::iterator it=x.begin();it!=x.end();it++)
		{
			a[*it-1]=1;
			if(it==x.begin())
			{
				temp+=findmin(*it-1,*(it+1)-1);
			}
			else
			if(it==x.end()-1)
			{
				temp+=findmin(*it-1,*(it-1)-1);
			}
			
		}

		for(i=0;i<N;i++)
		{
			if(a[i]==0)
			{
				temp+=findmin(i,-1);
			}
			
		}
		lcost+=temp/2;
	}
	bool operator <( Node &n)
	{
		if(lcost<=n.lcost)
			return true;
		else 
			return false;
	}
	void print()
	{
		cout<<"vector:"<<endl;
		for (vector<int>::iterator i=x.begin();i!=x.end();i++)
		{
			cout<<*i<<" "<<flush;
		}
		cout<<"cc="<<cc<<endl;
		cout<<"lcost="<<lcost<<endl;
	}

	vector<int>x;
	int cc;
	int lcost;
};
Node min;
void extends(vector<Node> &y)
{
	Node temp;
	for (int i=1;i<=5;i++)
	{
		temp=y[0];
		temp.add(i);
		if (temp.feasible())
		{
			cout<<"feasible"<<endl;
			y.push_back(temp);
			if (temp.x.size()==N)
			{
				temp.add(1);
				if(temp.cc<min.cc)
					min=temp;
			}
			
		}
	}
	y.erase(y.begin());
	sort(y.begin(),y.end());
}
void  greedy()
{
	int a[N]={0},min,MIN;
	for (int i=0;i<N;i++)
	{
		min=MAX;
		for (int j=0;j<N;j++)
		{	
			if (a[j]==1)
			 continue;
			else
				if(matrix[i][j]<min)
				{
					MIN=j;
					min=matrix[i][j];
				}
		}
		a[MIN]=1;
		up+=min;
	}
}
void main()
{
	greedy();
	min.cc=MAX;
	vector <Node> nodes;
	Node first;
	nodes.push_back(first);
	while (nodes.begin()!=nodes.end())
	{
		extends(nodes);
	}
	
	min.print();
}
